Small Dynamic Complexity Classes by Thomas Zeume

Author:Thomas Zeume
Language: eng
Format: epub
Publisher: Springer Berlin Heidelberg, Berlin, Heidelberg

The other formulas are very similar. This completes the construction of .

It remains to construct a quantifier-free dynamic program for an arbitrary semi-positive existential formula using quantifier-free programs for subgraphs. To this end let be an arbitrary semi-positive existential first-order formula. We show how to translate into an equivalent disjunction of formulas of the form

where each is a conjunction of atoms over and .

Observe that the quantifier-free part of each encodes a subgraph . Hence a graph G satisfies if and only if one of the graphs is a subgraph of G. Thus a program maintaining the query defined by can be constructed by combining the dynamic programs for all in a straightforward way.

We now sketch how to translate into the form stated above. First is rewritten as disjunction of conjunctive queries, that is as where each is a conjunction of positive literals and literals of the form . Afterwards each is rewritten into an equivalent disjunction over all equality types over the variables in , that is as

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.